/*
自己选择的路 ,跪着也要走完。朋友们 , 虽然这个世界日益浮躁起来,只
要能够为了当时纯粹的梦想和感动坚持努力下去 , 不管其它人怎么样,我
们也能够保持自己的本色走下去。
To the world , you will be a person , but to a person , you
will be the world .                               ——AKPower
*/
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <string>
#include <stack>
#include <set>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;

const int ChessBoard_Row = 13;
const int ChessBoard_Col = 26;
const int GridNuber = 9;
const char Comp_Char = 'X';
const char Human_Char = 'O';
const char Blank_Char = ' ';

class ChessBoard {
public:
	ChessBoard();

	bool isEmpty(int pos);
	bool isFull();
	bool canWin(char c);
	bool immediateComWin(int& bestMove);
	bool immediateHumanWin(int& bestMove);
	void placeComp(int pos);
	void placeHuman(int pos);
	void unPlace(int pos);
	void print();
private:
	vector<char> boardInOneDimens;
	vector<string> board;

};

ChessBoard::ChessBoard() {
	boardInOneDimens.resize(GridNuber);
	for (int i = 0; i < GridNuber; i++)
		boardInOneDimens[i] = ' ';
	vector<string>tmp = {
		"- - - - - - - - - - - - -",
		"|       |       |       |",
		"|       |       |       |",
		"|       |       |       |",
		"- - - - - - - - - - - - -",
		"|       |       |       |",
		"|       |       |       |",
		"|       |       |       |",
		"- - - - - - - - - - - - -",
		"|       |       |       |",
		"|       |       |       |",
		"|       |       |       |",
		"- - - - - - - - - - - - -"
	};
	board = tmp;
}
//check the posion is empty or not 
bool ChessBoard::isEmpty(int pos) {
	return boardInOneDimens[pos] == ' ';
}
//
bool ChessBoard::isFull() {
	for (int i = 0; i < GridNuber; i++) {
		if (boardInOneDimens[i] == ' ')
			return false;
	}
	return true;
}
//
bool ChessBoard::canWin(char c) {
	//check every row
	for (int i = 0; i <= 6; i+=3) {
		if (boardInOneDimens[i] == c&&boardInOneDimens[i] == boardInOneDimens[i + 1] &&
			boardInOneDimens[i] == boardInOneDimens[i + 2])
			return true;
	}
	//check every col
	for (int i = 0; i < 3; i++) {
		if (boardInOneDimens[i] == c&&boardInOneDimens[i] == boardInOneDimens[i + 3] &&
			boardInOneDimens[i] == boardInOneDimens[i + 6])
			return true;
	}
	//check every diagonals
	if (boardInOneDimens[0] == c&&boardInOneDimens[4] == c&&boardInOneDimens[8] == c)
		return true;
	if (boardInOneDimens[2] == c&&boardInOneDimens[4] == c&&boardInOneDimens[6] == c)
		return true;
	return false;
}
//
bool ChessBoard::immediateComWin(int& bestMove) {
	for (int i = 0; i < GridNuber; i++) {
		if (isEmpty(i)) {
			boardInOneDimens[i] =Comp_Char;
			bool Win = canWin(Comp_Char); 
			boardInOneDimens[i] = Blank_Char;   //backtraceing
			if (Win) {
				bestMove = i;
				return true;
			}
		}
	}
	return false;
}
//
bool ChessBoard::immediateHumanWin(int& bestMove) {
	for (int i = 0; i < GridNuber; i++) {
		if (isEmpty(i)) {
			boardInOneDimens[i] = Human_Char;
			bool Win = canWin(Human_Char);
			boardInOneDimens[i] = Blank_Char;   //backtraceing
			if (Win) {
				bestMove = i;
				return true;
			}
		}
	}
	return false;
}
//
void ChessBoard::placeComp(int pos) {
	boardInOneDimens[pos] = 'X';
}
//
void ChessBoard::placeHuman(int pos) {
	boardInOneDimens[pos] = 'O';
}
//
void ChessBoard::unPlace(int pos) {
	boardInOneDimens[pos] = ' ';
}
//
void ChessBoard::print() {
	int cnt = 0;
	for (int i = 2; i <= 10; i += 4) {
		for (int j = 4; j <= 20; j += 8) {
			board[i][j] = boardInOneDimens[cnt++];
		}
	}
	for (int i = 0; i < ChessBoard_Row; ++i) {
		cout << board[i] << endl;
	}
}

enum Role { Human, Comp };
static const int CompWin = 2;
static const int Draw = 1;
static const int HumanWin = 0;
class TicTacToe {
public:
	void start();
	bool handleGameOver();
	bool gameIsOver(bool &draw, Role &win);
	Role chooseFirstPlace();
	void compPlace();
	int getBestMove();
	void humanPlace();
	int getPlacePosition();
	void findCompMove(int& bestMove,int& value, int alpha, int beta);
	void findHumanMove(int& bestMove,int& value, int alpha, int beta);
private:
	ChessBoard board;
};

void TicTacToe::start() {
	Role firstPlace = chooseFirstPlace();
	if (firstPlace == Comp) {  // Choose computer to be the first
		compPlace();
	}
	while (1) {
		board.print();
		if (handleGameOver()) break;
		humanPlace();
		board.print();
		if (handleGameOver()) break;
		compPlace();
	}
}
Role TicTacToe::chooseFirstPlace() {
	int choose;
	while (1) {
		cout << "who will place first" << endl;
		cout << "0 : human first " << endl;
		cout << "1 : computer first" << endl;
		cin >> choose;
		if (choose == 0 || choose == 1) {
			cout << endl;
			break;
		}
		else
			cout << "error,please enter again" << endl;
	}
	return (Role)choose;
}
//
void TicTacToe::humanPlace() {
	int pos = getPlacePosition();
	board.placeHuman(pos);
	cout << "Your choice:" << endl;
}
//
int TicTacToe::getPlacePosition() {
	int m, n,pos;
	while (1) {
		cout << "It is your turn, please input where you want :" << endl;
		cout << "for example: 2 2 mean you want to add position 2 row,2 col:" << endl;
		cin >> m >> n;
		if (m < 0 || m>3 || n < 0 || n>3)
			cout << "error,please input again:" << endl;
		else {
			pos = (m - 1) * 3 + n - 1;
			if (board.isEmpty(pos))
				break;
			else
				cout << "error,please input again:" << endl;
		}
	}
	return pos;
}
//
void TicTacToe::compPlace() {
	int bestMove = getBestMove();
	board.placeComp(bestMove);
	cout << "the computer choice is: " << endl;
}
int TicTacToe::getBestMove() {
	int bestMove = 0, value = 0;
	findCompMove(bestMove,value,HumanWin, CompWin);
	return bestMove;
}
void TicTacToe::findCompMove(int& bestMove,int &value, int alpha, int beta) {
	if (board.isFull())
		value = Draw;
	else if (board.immediateComWin(bestMove))
		value = CompWin;
	else {
		value = alpha;
		for (int i = 0; i < GridNuber&&value < beta; i++) {
			if (board.isEmpty(i)) {
				board.placeComp(i);
				int tmp = -1, response = -1;  // Tmp is useless
				findHumanMove(tmp, response, value, beta);
				board.unPlace(i);
				if (response > value) {
					value = response;
					bestMove = i;
				}
			}
		}
	}
}

void TicTacToe::findHumanMove(int& bestMove,int & value, int alpha, int beta) {
	if (board.isFull())
		value=Draw;
	else if (board.immediateHumanWin(bestMove)){
		value=HumanWin;
	}
	else {
		value = beta; 
		for (int i = 0; i < GridNuber&&value>alpha; i++) {
			if (board.isEmpty(i)) {
				board.placeHuman(i);
				int tmp = -1, response = -1;  // Tmp is useless
				findCompMove(tmp, response, alpha, value);
				board.unPlace(i);
				if (response <value) {
					value = response;

					bestMove = i;
				}
			}
		}
	}
}
//
bool TicTacToe::gameIsOver(bool &draw, Role &win) {
	if (board.canWin(Comp_Char)) {
		win =Comp ;
		draw = false;
		return true;
	}
	else if (board.canWin(Human_Char)) {
		win = Human;
		draw = false;
		return true;
	}
	else if (board.isFull()) {
		draw = true;
		return true;
	}
	else {
		return false;
	}
}

bool TicTacToe::handleGameOver()  {
	bool draw = false;
	Role whoWin = Human;
	if (gameIsOver(draw, whoWin)) {
		if (draw) {
			cout << "Draw!" << endl;
		}
		else {
			if (whoWin == Comp) {
				cout << "You lose!" << endl;
			}
			else if (whoWin == Human) {
				cout << "Congratulations! You defeat the computer." << endl;
			}
		}
		return true;
	}
	else {
		return false;
	}
}

int main()
{
    IOS;
    while (1) {
		TicTacToe game;
		game.start();
		cout << "play again(Y or y):" << endl;
		char c;
		cin >> c;
		if (c != 'y'&&c !='Y') 
			break;
	}
    getchar();
    getchar();
    return 0;
}
